package com.leetcode.test.tree;

import org.junit.Assert;
import org.junit.Test;

/**
 * https://leetcode-cn.com/explore/learn/card/data-structure-binary-tree/3/solve-problems-recursively/12/
 * <p>
 * 解题：https://leetcode-cn.com/problems/maximum-depth-of-binary-tree/solution/er-cha-shu-de-zui-da-shen-du-by-leetcode/
 */
public class 二叉树的最大深度 extends 二叉树Case {

	@Test
	public void test() {
//		 3
//		/ \
//	   9  20
//		 /  \
//		15   7

//		返回其层次遍历结果：
//		[
//        [3],
//        [9,20],
//        [15,7]
//		]
		TreeNode n3  = new TreeNode(3);
		TreeNode n9  = n3.left = new TreeNode(9);
		TreeNode n20 = n3.right = new TreeNode(20);
		TreeNode n15 = n20.left = new TreeNode(15);
		TreeNode n7  = n20.right = new TreeNode(7);

		Assert.assertEquals(0, maxDepth(null));
		Assert.assertEquals(3, maxDepth(n3));
	}

	@Test
	public void test2() {
//		 1
//		/ \
//	   2   3
//	  /  \
//	 4    5

		TreeNode n1 = new TreeNode(1);
		TreeNode n2 = n1.left = new TreeNode(2);
		TreeNode n3 = n1.right = new TreeNode(3);
		TreeNode n4 = n2.left = new TreeNode(4);
		TreeNode n5 = n2.right = new TreeNode(5);

		Assert.assertEquals(3, maxDepth(n1));
	}

	// 官方题解
	public int maxDepth(TreeNode root) {
		if (root == null) return 0; // null节点第0层，往上层+1

		int leftLevel  = maxDepth(root.left);
		int rightLevel = maxDepth(root.right);

		return Math.max(leftLevel, rightLevel) + 1;
	}

//	public int maxDepth(TreeNode root) {
//		int maxLevel = helper(root, 1);
//		return Math.max(0, maxLevel);
//	}

	// 我的方法
//	private int helper(TreeNode node, int level) {
//		if (node == null) {
//			return level - 1;
//		}
//		if (node.left == null && node.right == null) {
//			// 最深层了
//			return level;
//		}
//
//		int leftLevel  = helper(node.left, level + 1);
//		int rightLevel = helper(node.right, level + 1);
//		int maxLevel   = Math.max(leftLevel, rightLevel);
//		return maxLevel;
//	}
}
